package com.chenken;


/**
 * 堆排序
 *		可以认为是选择排序的一种优化
 * 执行流程
 * 		1.对序列进行原地建堆
 * 		2.重复一下操作，直到堆的元素数量为1
 * 			2.1  交换堆顶元素与尾元素
 * 			2.2	堆的size-1
 * 			2.3 对0位置的元素进行siftdown操作
 */
public class HeapSort<T extends Comparable<T>> extends Sort<T>{

	private int heapSize;
	
	@Override
	protected void sort() {
		// 	原地建堆，自上而下的下滤
		heapSize = arrays.length;
		for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
			siftDown(i);
		}
		
		while (heapSize > 1) {
			// 	交换堆顶元素和尾部元素
			swap(0, --heapSize);

			// 	对0位置进行siftDown（恢复堆的性质）
			siftDown(0);
		}
	}
	
	private void siftDown(int index) {
		T element = arrays[index];
		
		int half = heapSize >> 1;
		while (index < half) { // index必须是非叶子节点
			// 	默认是左边跟父节点比
			int childIndex = (index << 1) + 1;
			T child = arrays[childIndex];
			
			int rightIndex = childIndex + 1;
			//	 右子节点比左子节点大
			if (rightIndex < heapSize && 
					compare(arrays[rightIndex], child) > 0) { 
				child = arrays[childIndex = rightIndex];
			}
			
			// 	大于等于子节点
			if (compare(element, child) >= 0) break;
			
			arrays[index] = child;
			index = childIndex;
		}
		arrays[index] = element;
	}
}
